package com.algorithm.merger;
/*
 *@Author:DOWN
 *@Date:2022/1/11 10:37
 *@Comment:归并排序
 */

import com.algorithm.testutils.ArrayGenerator;
import com.algorithm.testutils.SortingHelp;

import java.util.Arrays;

public class MergeSort {
    /**
     * 排序
     *
     * @param arr 数组
     * @param <E> 泛型
     */
    public static <E extends Comparable<E>> void sort(E[] arr) {
        //优化-2 内存优化 只开辟一次内存空间
        E[] temp = Arrays.copyOfRange(arr, 0, arr.length);
        sort(arr, 0, arr.length - 1, 1, temp);
    }

    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r, int depth, E[] temp) {
        if (l >= r) {
            return;
        }
        //int 越大可能类型range跃出
        int mid = l + (r - l) / 2;
        sort(arr, l, mid, depth + 1, temp);
        sort(arr, mid + 1, r, depth + 1, temp);
        //优化-1 已经有序无需排序
        if (arr[mid].compareTo(arr[mid + 1]) > 0) {
            merge(arr, l, mid, r, temp);
        }
    }

    /**
     * 自底向上的归并排序（与上差异：不用递归，java源生JVM 效率较上稍慢，C++较上稍快。）
     *
     * @param arr 元素组
     * @param <E> 泛型
     */
    public static <E extends Comparable<E>> void sortBU(E[] arr) {
        //开辟缓存区间
        E[] temp = Arrays.copyOfRange(arr, 0, arr.length);
        //元素组长度
        int l = arr.length;
        //自底向上 分割算法
        //分组 遍历数组长度
        for (int sz = 1; sz < l; sz += sz) {
            //合并 两个 sz 长度区间内的元素：[i,i+sz-1] merge [i+sz,i+sz+sz]
            //当i+sz<l 时 例如：arr。length=11 sz=3  i=9 ，则跳出merge
            for (int i = 0; i + sz < l; i += sz + sz) {
                //当 第一个区间的尾元素 大与 第二个区间的头元素时，说明 两个区间存在待排序元素，需要归并（merger）排序
                if(arr[i+sz-1].compareTo(arr[i+sz])>0)
                //Math.min:当 mid+sz 越过 l 时，取l-1。
                {
                    merge(arr, i, i + sz - 1, Math.min(i + sz - 1 + sz, l - 1), temp);
                }
            }
        }
    }

    /**
     * 合并两个有序区间-归并
     *
     * @param arr 数组
     * @param l   arr[l,mid]
     * @param r   arr[mid+1,r]
     * @param <E> 泛型
     */
    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r, E[] temp) {
        //copyOfRange:从下标from开始复制，复制到上标to，生成一个新的数组。
        //包括下标from，不包括上标to。
        //temp 只复制了 l->r 范围内的数据
        //  -l 是偏移量 temp 只复制 Range内 的数据
        // 优化后无偏移量 -l
        System.arraycopy(arr, l, temp, l, r - l + 1);
        int i = l, j = mid + 1;
        //每轮循环为arr[k]赋值
        //有序数列采用以下排序方法
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                arr[k] = temp[j];
                j++;
            } else if (j > r) {
                arr[k] = temp[i];
                i++;
            } else if (temp[i].compareTo(temp[j]) <= 0) {
                arr[k] = temp[i];
                i++;
            } else {
                arr[k] = temp[j];
                j++;
            }
        }
    }

    public static void main(String[] args) throws Exception {
        //插入排序
        //Integer[] arr0 = ArrayGenerator.getRandomArrays(100000000, 100000);
        Integer[] arr2 = ArrayGenerator.getRandomArrays(100000000, 100000);
        //arr0 = new Integer[]{7, 6, 5, 4, 3, 2, 1, 0};
        //Integer[] arr1 =  ArrayGenerator.getRandomArrays(100000,100000000);
        //Integer[] arr2 =  ArrayGenerator.getRandomArrays(100000,100000000);
        //SortingHelp.sortTest("com.algorithm.yyy.InsertionSort","sort",arr0);
        //选择排序
        //SortingHelp.sortTest("com.algorithm.yyy.SelectionSort","sort",arr1);
        //归并排序 1亿以上时 性能开始出现变化
        //SortingHelp.sortTest("com.algorithm.merger.MergeSort", "sort", arr0);//over:43.5350596s
        SortingHelp.sortTest("com.algorithm.merger.MergeSort", "sortBU", arr2);//over:46.5293407s
        //System.out.println(Arrays.toString(arr0));
    }
}
